class NumArray {
private:
    vector<int> tree;
    int n;
    void build(vector<int>& nums,int idx,int l,int r){
        if(l == r){
            tree[idx] = nums[l];
            return;
        }
        int mid = l + (r - l) / 2;
        build(nums,idx * 2 + 1,l,mid);
        build(nums,idx * 2 + 2,mid + 1,r);
        tree[idx] = tree[idx * 2 + 1] + tree[idx * 2 + 2];
    }
    void change(int index,int val,int l,int r,int idx){
        if(l == r){
            tree[idx] = val;
            return;
        }
        int mid = l + (r - l) / 2;
        if(index <= mid){
            change(index,val,l,mid,idx * 2 + 1);
        }else{
            change(index,val,mid+1,r,idx * 2 + 2);
        }
        tree[idx] = tree[idx * 2 + 1] + tree[idx * 2 + 2];
    }
    int range(int start,int end,int l,int r,int idx){
        if(start > r || end < l){
            return 0;
        }
        if(start <= l && end >= r){
            return tree[idx];
        }
        int mid = l + (r - l) / 2;
        return range(start,end,l,mid,idx * 2 + 1)
            +  range(start,end,mid+1,r,idx * 2 + 2);
    }
public:
    NumArray(vector<int>& nums) 
        :n(nums.size())
        ,tree(4 * nums.size())
        
    {
        build(nums,0,0,n-1);
    }
    
    void update(int index, int val) {
        change(index,val,0,n-1,0);
    }
    
    int sumRange(int left, int right) {
        return range(left,right,0,n-1,0);
    }
};
